#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> numc;
    vector<int> rets;
    vector<int> retc, retn;

    void _countSmaller(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;

        int mid = (right + left) / 2;
        _countSmaller(nums, left, mid);
        _countSmaller(nums, mid + 1, right);

        int i = left, l = left, r = mid + 1;
        while (l <= mid && r <= right)
        {
            if (nums[l] <= nums[r])
            {
                numc[i] = nums[r];
                retn[i++] = retc[r++];
            }
            else
            {
                rets[retc[l]] += right - r + 1;
                numc[i] = nums[l];
                retn[i++] = retc[l++];
            }
        }


        while (l <= mid) numc[i] = nums[l], retn[i++] = retc[l++];
        while (r <= right) numc[i] = nums[r], retn[i++] = retc[r++];
        for (int j = left; j <= right; j++) nums[j] = numc[j], retc[j] = retn[j];
    }
    vector<int> countSmaller(vector<int>& nums) {
        numc = nums;
        for (int i = 0; i < nums.size(); i++) retc.push_back(i);
        retn = retc;
        rets.resize(nums.size());
        _countSmaller(nums, 0, nums.size() - 1);

        return rets;
    }
};

int main()
{
    Solution s;
    vector<int> v({ 5,2,6,1 });
    s.countSmaller(v);
    return 0;
}